package leetcode.动态规划.simple;

/**
 * @author wangmaolin1
 * @date 2022/1/16 上午9:49
 */
public class _1137第N个泰波那契数 {
    /*
         泰波那契序列 Tn 定义如下： 
        T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
        给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
     */

    public static int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int[] dp = new int[3];
        dp[1] = 1;
        dp[2] = 1;
        int ans = 1;
        for (int i = 3; i < n + 1; i++) {
            ans = dp[0] + dp[1] + dp[2];
            dp[0] =  dp[1];
            dp[1] =  dp[2];
            dp[2] = ans;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(tribonacci(25));
    }
}
